package com.zecan.kruskal;

import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/13
 * \* Time: 17:08
 * \* Description:
 * \
 */
public class KruskalDemo {
    private int edgeNum; // 边的个数
    private int[][] matrix ;; // 邻接矩阵
    private char[] vertex; // 存放顶点的数组
    private static final int INF = 65563; // 当邻接矩阵边与边之间没有相连时 值为INF
    public static void main(String[] args) {
        char[] vertexs = new char[] {'A','B','C','D','E','F','G'};
        int[][] matrix = new int[][]{
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0},
        };
        KruskalDemo kruskalDemo = new KruskalDemo(vertexs, matrix);
        kruskalDemo.print();
        System.out.println(Arrays.toString(kruskalDemo.getEdges()));
        kruskalDemo.kruskal();

    }
    public KruskalDemo( char[] vertex, int[][] matrix) {
            int vLen = vertex.length;
            this.vertex = new char[vLen];
            this.matrix = new int[vLen][vLen]; // 初始化邻接矩阵和顶点数组
        int i = 0, j = 0;
        for(char c : vertex) {
            this.vertex[i++] = c;
        }
        // 初始化邻接矩阵
       for(i = 0 ; i < vLen; i++) {
           for( j = 0; j < vLen; j++) {
               this.matrix[i][j] = matrix[i][j];
           }
       }
       // 统计边的个数
       for(i = 0; i < vLen; i++) {
           for(j = i + 1 ; j < vLen ;j++) {
                if(this.matrix[i][j] != INF) {
                    edgeNum++;
                }
           }
       }
    }
    public void kruskal() {
        int index = 0;
        int[] ends = new int[edgeNum]; // 存放结尾字符
        Edata[] edges = getEdges(); // 获取所有边和权重的集合的数组
        Edata[] res = new Edata[edgeNum]; // 存放顶点和边的结果
        sortEdge(edges); // 将边与权值的集合进行排序 根据 权值从小到大
        int p1 = 0; // 指向第一个结点
        int p2 = 0; // 指向第二个结点
        for (int i = 0; i < edgeNum; i++) {
            p1 = getPosition(edges[i].start);
            p2 = getPosition(edges[i].end);
            int m = getEnd(ends,p1); // 获取第一个结点的结束结点
            int n = getEnd(ends,p2); // 获取第二个节点的结束节点
            if(m != n) { // 当两个不相同时 就是不构成回路
                ends[m] = n; // 此时将 m 的结束节点设置为 n
                res[index] = edges[i]; // 将结点保存
                index++;
            }
        }
        for (int i = 0; i < index; i++) {
            System.out.println(res[i]);
        }
    }
    public  void print() {
        int i , j;
        for ( i = 0; i < vertex.length; i++) {
            for ( j = 0; j < vertex.length; j++) {
                    System.out.print(matrix[i][j] + "\t");
            }
            System.out.println();
        }
    }
    /**
     * 将边的权重的从小到大排序
     * @param edges 边与边的集合
     * @return void
     * @author 
     * @creed: Talk is cheap,show me the code
     * @date  
     */
    private void sortEdge(Edata[] edges) {
        boolean flag = false;
        for (int i = 0; i < edges.length -1 ; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                    if(edges[j].weight > edges[j + 1].weight) {
                        Edata temp = edges[j];
                        edges[j] = edges[j+1];
                        edges[j + 1] = temp;
                        flag = true;
                    }
            }
            if(flag) {
                flag =false;
            }else{
                break;
            }
        }
    }
    /**
     * 传递一个顶点 返回其在顶点数组中的下标
     * @param ch 需要查找的顶点字符
     * @return 返回ch 的下标位置 找不到返回-1
     * @author
     * @creed: Talk is cheap,show me the code
     * @date
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertex.length; i++) {
            if(vertex[i] == ch) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 此方法的作用是存放入所有顶点之间边的集合 和 其所对应的权值
     * @return 返回存入进去的边集合
     * @author
     * @creed: Talk is cheap,show me the code
     * @date
     */
    private Edata[] getEdges() {
        int  index = 0;
        Edata[] edges = new Edata[edgeNum];
        for (int i = 0; i < vertex.length; i++) {
            for (int j = i + 1; j < vertex.length; j++) {
                    if(matrix[i][j] != INF) {
                        edges[index++] = new Edata(vertex[i],vertex[j],matrix[i][j]);
                    }
            }
        }
        return edges;
    }
    private int getEnd(int[] ends, int i) {
        while(ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }
}

class Edata {
    char start;
    char end;
    int weight;// 边与边之间的权重

    public Edata(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Edata{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
